package com.leetcode;

import com.alibaba.fastjson.JSON;
import com.common.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 寻找重复的子树
 * @author caiwei
 * @date 2021/9/9 15:49
 */
public class LeetCode652 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);

        TreeNode node_left = new TreeNode(2);
        node.left = node_left;
        node_left.left = new TreeNode(4);

        TreeNode node_right = new TreeNode(3);
        node.right = node_right;
        TreeNode node_right_left = new TreeNode(2);
        node_right.left = node_right_left;
        node_right.right = new TreeNode(4);
        node_right_left.left = new TreeNode(4);
        System.out.println(JSON.toJSONString(node));

        List<TreeNode> duplicateSubtrees = new LeetCode652().findDuplicateSubtrees(node);
        for (TreeNode duplicateSubtree : duplicateSubtrees) {
            System.out.println(JSON.toJSONString(duplicateSubtree));
        }
    }

    //存储所有节点情况
    HashMap<String,Integer> treeNodeMap = new HashMap<>();
    //重复节点
    List<TreeNode> treeNodes = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        computerNode(root);
        return treeNodes;
    }

    //遍历出所有的节点信息
    public String computerNode(TreeNode node){
        if (node == null) {
            return "";
        }
        //递归取出所有的节点信息
        String left = computerNode(node.left);
        String right = computerNode(node.right);
        String key = ""+node.val + "-l" + left + "-r" + right;

        System.out.println(key);
        int value = treeNodeMap.getOrDefault(key, 0) + 1;
        treeNodeMap.put(key, value);
        //当有重复的时候就记录下来且不重复记录
        if (value == 2) {
            treeNodes.add(node);
        }
        return key;
    }

}
